package com.szp.lagou.mongodb.mongolearn.entity;

public class Test {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dp = new int[m][n];
        int sum = 0;
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(mat[i][j] == 0)
                    continue;
                dp[i][j] = j > 0 ? dp[i][j-1] +1 : 1;
                int min = Integer.MAX_VALUE;
                for(int k = i; k >=0; k--){
                    min = Math.min(dp[k][j], min);
                    sum += min;
                    if(min == 0)
                        break;
                }
            }
        }

        return sum;
    }

    public static void main(String[] args) {
        int[][] mat = new int[][]{
            {0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,1},
            {0,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0},
            {1,1,0,1,0,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1},
            {0,1,1,1,1,0,1,1,1,1,1,1,0,1,0,0,0,1,1,1,1,0},
            {1,1,1,1,1,0,0,0,1,0,1,0,0,1,0,0,1,1,1,1,1,1},
            {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1},
            {1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0},
            {1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,1,1,1,0,0,1},
            {1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,0,1},
            {0,1,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1},
            {1,0,1,1,1,1,0,1,1,1,1,0,0,1,1,1,1,0,1,1,1,0}};
        Test test = new Test();
        int res = test.numSubmat(mat);
        System.out.println(res);
        System.out.println("######################");
    }
     
}